package main

import (
	"fmt"
	"hash/fnv"
)

// BloomFilter 布隆过滤器结构体
type BloomFilter struct {
	size   uint64 // 位数组的大小
	bits   []bool // 用布尔切片作为位数组
	hashes uint64 // 哈希函数的数量
}

// NewBloomFilter 初始化布隆过滤器
func NewBloomFilter(size uint64, hashes uint64) *BloomFilter {
	return &BloomFilter{
		size:   size,
		bits:   make([]bool, size),
		hashes: hashes,
	}
}

// Hash 计算字符串的哈希值
func Hash(s string, seed uint64) uint64 {
	h := fnv.New64a()
	h.Write([]byte(s))
	return h.Sum64() ^ seed // 利用种子来变换结果
}

// Add 添加一个元素到布隆过滤器
func (bf *BloomFilter) Add(item string) {
	for i := uint64(0); i < bf.hashes; i++ {
		hash := Hash(item, i) % bf.size
		bf.bits[hash] = true // 将对应的位设置为 true
	}
}

// Check 检查元素是否在布隆过滤器中
func (bf *BloomFilter) Check(item string) bool {
	for i := uint64(0); i < bf.hashes; i++ {
		hash := Hash(item, i) % bf.size
		if !bf.bits[hash] {
			return false // 如果某个位为 false，肯定不在集合中
		}
	}
	return true // 可能在集合中
}

func main() {
	bloomFilter := NewBloomFilter(1000, 10) // 创建布隆过滤器，位数组大小为 1000，使用 10 个哈希函数

	// 添加元素
	bloomFilter.Add("Hello")
	bloomFilter.Add("World")

	// 检查元素
	fmt.Println(bloomFilter.Check("Hello")) // 输出: true (可能在集合中)
	fmt.Println(bloomFilter.Check("World")) // 输出: true (可能在集合中)
	fmt.Println(bloomFilter.Check("Go"))    // 输出: false (肯定不在集合中)
}
